﻿#define _CRT_SECURE_NO_WARNINGS 1
#include <algorithm>
#include <ios>
#include <iostream>
#include <unordered_map>
#include <vector>
using namespace std;

int main() {
    //dp的经典问题
    string s, t;
    cin >> s >> t;
    int n = s.size(), m = t.size();
    vector<vector<int>> dp(n + 1, vector<int>(m + 1, 0));
    for (int i = 0; i <= n; i++) dp[i][0] = i;//初始化，一个空串变为s所需要的次数
    for (int j = 0; j <= m; j++) dp[0][j] = j;//初始化，一个空串变为t所需要的次数

    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= m; j++)
        {
            //状态转移，替换字符视为dp[i-1][j-1]+1，删除字符可以视为s串后面插入一个字符即为dp[i-1][j]+1
            //插入字符可以视为t串后面插入字符即为dp[i][j-1]+1，注意相等的比较策略
            if (s[i - 1] == t[j - 1]) dp[i][j] = min(dp[i - 1][j - 1], min(dp[i - 1][j] + 1, dp[i][j - 1] + 1));
            else dp[i][j] = min(dp[i - 1][j - 1], min(dp[i - 1][j], dp[i][j - 1])) + 1;
        }
    }
    cout << dp[n][m];
    return 0;
}
// 64 位输出请用 printf("%lld")
//1 1 1
//1 0 0
//1 0 0
//1 0 0